package com.algorithm.dp;

import static java.lang.Math.max;

/**
 * 最长回文子序列:
 * 对于字符串s,i、j分别为字符串首尾指针,dp[i][j]为以i开头j结尾的子字符串的最长回文子序列,
 * 状态转移方程为:
 *  if(s[i] == s[j]) dp[i][j] = dp[i+1][j-1] +2
 *  else dp[i][j] = max{dp[i+1][j],dp[i][j-1]}
 *
 *  1.可以使用二维数组进行记录,因为i始终小于j,所以只有一半用到了
 *  2.扫描时根据dp[i][j] 的依赖关系,可以得出二维数组的扫描顺序
 *  3.根据题目含义,可以推出二维数组初始化行/列/值
 *  4.dp最终结果可能是dp右下角值,也可能是数组中出现的最大值
 *
 *  5.对于dp[i][j]只依赖于二维数组中前后n行的情况,可以使用n维滚动数组优化
 *  6.优化为一维数组,则dp[i][j]最多只能依赖于数组中前一列或前一行的子结果
 */
public class LongestPalindromeSequence {
    public static void main(String[] args) {
        String s = "adcbcdf";
        int max = palindromeSequence(s);
        System.out.println(max);
    }

    private static int palindromeSequence(String s) {
        if (s.length() < 2) {
            return s.length();
        }
        int[][] dp = new int[s.length()][s.length()];
        for (int i = 0; i < s.length(); i++) {
            dp[i][i] = 1;
        }
        int max = 1;
        /**
         * 也可以这样扫描:
         * for (int i = s.length() - 2; i >= 0; i--) {
            for (int j = i+1; j < s.length(); j++) {

         还可以优化为二维滚动数组
         */
        for (int j = 1; j < s.length(); j++) {
            for (int i = j - 1; i >= 0; i--) {
                if (s.charAt(i) == s.charAt(j)) {
                    dp[i][j] = dp[i + 1][j - 1] + 2;
                } else {
                    dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
                }
                if (max < dp[i][j]) {
                    max = dp[i][j];
                }
            }
        }
        for (int i = 0; i < dp.length; i++) {
            for (int j = 0; j < dp[0].length; j++) {
                System.out.print(dp[i][j]);
            }
            System.out.println();
        }
        return max;
    }
}
